package com.wwz.leetcode;

import org.junit.Test;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class LeetCode20 {
    // "()[]{}"
    public boolean isValid(String s) {
        int length = s.length();
        if (length % 2 != 0) {
            return false;
        }

        Map<Character, Character> pairsMap = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        // 双端队列
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (pairsMap.containsKey(s.charAt(i)) && !stack.isEmpty() && stack.peek().equals(pairsMap.get(s.charAt(i)))) {
                stack.remove();
            } else {
                // 从头部压入元素
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }

    @Test
    public void test() {
        System.out.println(isValid("[()]"));

    }
}
